package com.example.Arithmetic.Lettcode;

import com.example.Arithmetic.Arithmetic.TreeNode;

import java.util.Arrays;
import java.util.List;

/**
 * 日期：2023/10/15
 * 时间：10:24
 * 描述：根据中序和后序遍历结果构造一棵二叉树
 */
public class E04Lettcode106 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) {
            return null;
        }
        int root = postorder[postorder.length - 1];
        TreeNode treeNode = new TreeNode(root);
        for (int i = 0; i < postorder.length; i++) {
            if (inorder[i] == root) {
                int[] inLeft = Arrays.copyOfRange(inorder, 0, i);
                int[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);
                int[] posLeft = Arrays.copyOfRange(postorder, 0,i);
                int[] posRight = Arrays.copyOfRange(postorder, i, postorder.length-1);

                treeNode.left = buildTree(inLeft, posLeft);
                treeNode.right = buildTree(inRight, posRight);
                break;
            }

        }
        return treeNode;
    }

    public static void main(String[] args) {
        E04Lettcode106 e04Lettcode106=new E04Lettcode106();
        int[] i=new int[]{3,9,20,15,7};
        int[] j=new int[]{9,3,15,20,7};
        TreeNode treeNode = e04Lettcode106.buildTree(i, j);
        E04Lettcode144 e=new E04Lettcode144();
        List<Integer> integerList = e.preorderTraversal2(treeNode);
        System.out.println(integerList);
    }
}

